﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using Leetcode_Array.Script.BinaryTreeCode;

namespace Leetcode_Array.Script.GreedyCode
{
    class Hard
    {
        //==============================================力扣53 最大子序和
        //给定一个整数数组nums,找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和
        public int MaxSUbArray(int[] nums)
        {//暴力法
            int result = int.MinValue;
            int count = 0;
            for(int i = 0;i<nums.Length;i++)
            {// 设置起始位置
                count = 0;
                for(int j = i;j < nums.Length;j++)
                {// 每次从起始位置i开始遍历寻找最大值
                    count += nums[j];
                    result = count > result ? count : result;
                }
            }
            return result;
        }
        public int MaxSubArray_2(int[] nums)
        {//贪心算法
            //局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。
            //全局最优：选取最大“连续和”
            //局部最优的情况下，并记录最大的“连续和”，可以推出全局最优。

            int result = int.MinValue;
            int count = 0;
            for(int i = 0;i<nums.Length;i++)
            {
                count += nums[i];
                if (count > result)// 取区间累计的最大值（相当于不断确定最大子序终止位置）
                    result = count;
                if (count <= 0)// 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
                    count = 0;
                
            }
            return result;
        }

        //====================================力扣55 跳跃游戏
        //给定一个非负整数数组，你最初位于数组的第一个位置
        //数组中的每个元素代表你在该位置可以跳跃的最大长度
        //判断你是否能到达最后一个位置       
        public bool CanJump(int[] nums)
        {//思路：每次取最大跳跃步数的话，这个就是可以跳跃的覆盖范围
         //那么问题就是跳跃范围是否可以覆盖到终点
         //局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。

            int cover = 0;
            if (nums.Length == 1)// 只有一个元素，就是能达到
                return true;
            for (int i = 0; i <= cover; i++)  // 注意这里是小于等于cover
            {
                cover = Math.Max(cover, i + nums[i]);
                if (cover >= nums.Length - 1)// 说明可以覆盖到终点了
                    return true;
            }
            return false;
        }
        //=================================力扣45 跳跃游戏2
        //给定一个非负整数数组nums，你最初位于数组的第一个位置
        //数组中的每个元素代表你在该位置可以跳跃的最大长度
        //你的目标是使用最少的跳跃次数到达数组的最后一个位置
        //假设你总是可以到达数组的最后一个位置
        public int Jump(int[] nums)
        {//贪心的思路，局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。整体最优：一步尽可能多走，从而达到最小步数。
            //以最小的步数增加最大的覆盖范围，直到覆盖范围覆盖了终点
            if (nums.Length == 1)
                return 0;
            int curDistance = 0; //当前覆盖最远距离下标
            int ans = 0;        //记录走的最大步数
            int nextDistance = 0;//下一步覆盖最远距离下标
            for (int i = 0; i < nums.Length; i++)
            {
                //更新下一步覆盖最远距离下标
                nextDistance = Math.Max(nums[i] + i, nextDistance);
                if(i == curDistance)//遇到当前覆盖最远距离下标
                {
                    if (curDistance != nums.Length - 1)
                    {
                        ans++;
                        curDistance = nextDistance;
                        if (nextDistance >= nums.Length - 1)
                            break;
                    }
                    else
                        break;
                }
            }
            return ans;
        }
        public int Jump_1(int[] nums)
        {//当移动下标指向nums.size - 2时:
            //如果移动下标等于当前覆盖最大距离下标， 需要再走一步（即ans++），因为最后一步一定是可以到的终点。（题目假设总是可以到达数组的最后一个位置）
            //如果移动下标不等于当前覆盖最大距离下标，说明当前覆盖最远距离就可以直接达到终点了，不需要再走一步

            int curDistance = 0;//当前覆盖的最远距离下标
            int ans = 0;        //记录走的最大步数
            int nextDistance = 0;//下一步覆盖的最远距离下标
            for(int i = 0;i<nums.Length - 1;i++)//这里是小于nums.length -1 .
            {
                nextDistance = Math.Max(nums[i] + i, nextDistance);// 更新下一步覆盖的最远距离下标
                if (i == curDistance) // 遇到当前覆盖的最远距离下标
                {
                    curDistance = nextDistance;// 更新当前覆盖的最远距离下标
                    ans++;
                }
            }
            return ans;
        }

        //======================================力扣134 加油站
        //在一条环路上有N个加油站，其中第i个加油站有汽油gas[i]升
        //你有一辆油箱容量无限的骑车，从第i个加油站开往第i+1个加油站需要消耗汽油cost[i]升。
        //你从其中的一个加油站出发，开始时油箱为空。
        //如果你可以绕环路行驶一周，则返回出发时加油站的变化，否则返回-1
        public int CanCompleteCircuit(int[] gas, int[] cost)
        {//暴力法
            //for循环适合模拟从头到尾的遍历，而while循环适合模拟环形遍历，要善于使用while！
            for (int i = 0;i< cost.Length;i++)
            {
                int rest = gas[i] - cost[i];//记录剩余油量
                int index = (i + 1) % cost.Length;
                while(rest > 0 && index != i)// 模拟以i为起点行驶一圈
                {
                    rest += gas[index] - cost[index];
                    index = (index + 1) % cost.Length;
                }
                // 如果以i为起点跑一圈，剩余油量>=0，返回该起始位置
                if (rest >= 0 && index == i)
                    return i;
            }
            return -1;
        }

        public int CanCompleteCircuit_2(int[] gas, int[] cost)
        {//贪心算法

            int curSum = 0;
            int min = int.MaxValue;
            for(int i = 0;i<gas.Length;i++)
            {
                int rest = gas[i] - cost[i];
                curSum += rest;
                if (curSum < min)
                    min = curSum;
            }

            if (curSum < 0)//如果gas的总和小于cost总和，那么无论从哪里出发，一定是跑不了一圈的
                return -1;
            if (min >= 0)//rest[i] = gas[i]-cost[i]为一天剩下的油，i从0开始计算累加到最后一站，如果累加没有出现负数，说明从0出发，油就没有断过，那么0就是起点。
                return 0;

            //如果累加的最小值是负数，汽车就要从非0节点出发，从后向前，看哪个节点能这个负数填平，能把这个负数填平的节点就是出发节点。
            for (int i = gas.Length - 1; i >= 0; i++)
            {
                int rest = gas[i] - cost[i];
                min += rest;
                if (min >= 0)
                    return i;
            }
            return -1;
        }

        public int CanCompleteCircuit_3(int[] gas, int[] cost)
        {//贪心算法
            //如果总油量减去总消耗大于等于零那么一定可以跑完一圈，说明 各个站点的加油站 剩油量rest[i]相加一定是大于等于零的。
            //每个加油站的剩余量rest[i]为gas[i] - cost[i]。
            //i从0开始累加rest[i]，和记为curSum，一旦curSum小于零，说明[0, i]区间都不能作为起始位置，起始位置从i+1算起，再从0计算curSum。

            int start = 0;
            int rest = 0;
            int total = 0;
            for(int i = 0;i<gas.Length;i++)
            {
                rest += gas[i] - cost[i];
                total += gas[i] - cost[i];
                if (rest < 0)
                {// 当前累加rest[i]和 curSum一旦小于0
                    start = i + 1;// 起始位置更新为i+1
                    rest = 0; // rest从0开始
                }
            }

            if (total < 0)
                return -1;//说明怎么走都不能跑一圈
            return start;
        }

        //=======================================力扣435 无重叠区间
        //给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠
        //可以认为区间的重点总是大于它的起点
        //区间[1,2]和[2,3】边界相互接触，但没有相互重叠。
        public int EraseOverlapIntervals(int[][] intervals)
        {//思路：按照右边界排序，从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。
         //右边界排序之后，局部最优：优先选右边界小的区间，所以从左向右遍历，留给下一个区间的空间大一些，从而尽量避免交叉。全局最优：选取最多的非交叉区间。

            int len = intervals.Length;
            if (len == 0)
                return 0;
            //按右边界排序
            Array.Sort(intervals, new CompareMethod());
            
            int count = 1;
            int end = intervals[0][1];//记录区间分割点
            for(int i = 1;i<len;i++)
            {
                if(end <= intervals[i][0])
                {
                    end = intervals[i][1];
                    count++;
                }
            }
            return len - count;
        }

        public class CompareMethod : IComparer<int[]>
        {
            public int Compare(int[] x, int[] y)
            {
                return x[1] - y[1];
            }
        }

        //=======================================力扣452 用最少数量的箭引爆气球
        //在二维空间中有许多球形的气球。对于每个气球，提供的输入是水平方向上的，气球直径的开始和结束坐标。
        //由于它是水平的，所以纵坐标并不重要，因此只要知道开始和结束的横坐标就足够了。开始坐标总是小于结束坐标
        //一支弓箭可以沿着x轴从不同点完全垂直地射出。
        //在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足  xstart ≤ x ≤ xend，则该气球会被引爆。
        //可以射出的弓箭的数量没有限制。 弓箭一旦被射出之后，可以无限地前进。我们想找到使得所有气球全部被引爆，所需的弓箭的最小数量。
        //给你一个数组 points ，其中 points [i] = [xstart,xend] ，返回引爆所有气球所必须射出的最小弓箭数。
        public int FindMinArrowShots(int[][] points)
        {//局部最优：当气球出现重叠，一起射，所用弓箭最少。全局最优：把所有气球射爆所用弓箭最少。
            if (points.Length == 0)
                return 0;

            //既然按照起始位置排序，那么就从前向后遍历气球数组，靠左尽可能让气球重复。
            Array.Sort(points, new Compared());

            int result = 1;//至少要一支箭
            for(int i = 1;i<points.Length;i++)
            {
                if (points[i][0] > points[i - 1][1])//注意题目中说的是：满足 xstart ≤ x ≤ xend，则该气球会被引爆。那么说明两个气球挨在一起不重叠也可以一起射爆，
                    result++;// 气球i和气球i-1不挨着，注意这里不是>=
                else
                    points[i][1] = Math.Min(points[i - 1][1], points[i][1]);//更新重叠气球最小右边界
            }
            return result;
        }
        public class Compared : IComparer<int[]>
        {
            public int Compare(int[] x, int[] y)
            {
                if (x[0] < y[0])
                    return -1;
                else
                    return 1;
            }
        }

        //==================================================力扣763 划分字母区间
        //字符串s由小写字母组成，
        //我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
        //返回一个表示每个字符串片段的长度的列表
        public IList<int> PartitionLabels(string s)
        {//如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。
            int[] hash = new int[26];// i为字符，hash[i]为字符出现的最后位置

            for (int i = 0;i<s.Length;i++)
            {// 统计每一个字符最后出现的位置
                hash[s[i] - 'a'] = i;
            }

            List<int> result= new List<int>();
            int left = 0;
            int right = 0;
            for(int i = 0;i<s.Length;i++)
            {
                right = Math.Max(right, hash[s[i] - 'a']);// 找到字符出现的最远边界
                if (i == right)
                {
                    result.Add(right - left + 1);
                    left = i + 1;
                }
            }
            return result;
        }


        //=================================================力扣56 合并区间
        //以数组 intervals表示若干个区间的集合，其中单个区间为intervals[i] = [starti, endi]。
        //请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组恰好覆盖输入中的所有区间
        public int[][] Merge(int[][] intervals)
        {
            
            List<int[]> result = new List<int[]>();
            if (intervals.Length == 0)
                return result.ToArray();

            //按照左边界排序，排序之后局部最优：每次合并都取最大的右边界，这样就可以合并更多的区间了，整体最优：合并所有重叠的区间。
            Array.Sort(intervals, new Compared());

            bool flag = false;// 标记最后一个区间有没有合并
            int len = intervals.Length;

            for(int i = 1;i<len;i++)
            {
                int start = intervals[i - 1][0];// 初始为i-1区间的左边界
                int end = intervals[i - 1][1];// 初始i-1区间的右边界
                while (i < len && intervals[i][0] <= end)
                {// 合并区间
                    end = Math.Max(end, intervals[i][1]);// 不断更新右区间
                    if (i == len - 1)
                        flag = true;// 最后一个区间也合并了
                    i++;// 继续合并下一个区间
                }
                // start和end是表示intervals[i - 1]的左边界右边界，所以最优intervals[i]区间是否合并了要标记一下
                result.Add(new int[2] { start, end });
            }
            // 如果最后一个区间没有合并，将其加入result
            if (flag == false)
                result.Add(new int[2] { intervals[len - 1][0], intervals[len - 1][1] });

            return result.ToArray();
        }

        //===========================================力扣958 监控二叉树
        //给定一个二叉树，我们在树的节点上安装摄像头
        //每个摄像头可以监视其父节点、自身以及直接子对象
        //计算监控所有节点所需要的最小摄像头数量
        public int MinCameraCover(TreeNode root)
        {
            //从下往上看，局部最优：让叶子节点的父节点安摄像头，所用摄像头最少，整体最优：全部摄像头数量所用最少！
            //从下往上遍历即后序遍历
            result = 0;

            if(Traversal(root) == 0)
            {// root 无覆盖
                result++;
            }
            return result;

        }
        int result;
        public int Traversal(TreeNode cur)
        {
            //0：该节点无覆盖
            //1：本节点有摄像头
            //2：本节点有覆盖

            //空节点，该节点有覆盖
            if (cur == null)
                return 2;

            int left = Traversal(cur.left);
            int right = Traversal(cur.right);

            //左右节点都有覆盖,那么此时中间节点应该就是无覆盖的状态了。
            if (left == 2 && right == 2)
                return 0;

            //左右节点至少有一个无覆盖的情况,则中间节点应该放摄像头
            // left == 0 && right == 0 左右节点无覆盖
            // left == 1 && right == 0 左节点有摄像头，右节点无覆盖
            // left == 0 && right == 1 左节点有无覆盖，右节点摄像头
            // left == 0 && right == 2 左节点无覆盖，右节点覆盖
            // left == 2 && right == 0 左节点覆盖，右节点无覆盖
            if (left == 0 || right == 0)
            {
                result++;
                return 1;
            }

            //左右节点至少有一个有摄像头,中间节点应该是覆盖状态
            // left == 1 && right == 2 左节点有摄像头，右节点有覆盖
            // left == 2 && right == 1 左节点有覆盖，右节点有摄像头
            // left == 1 && right == 1 左右节点都有摄像头
            if (left == 1 || right == 1)
            {
                return 2;
            }

            return -1;
        }
    }
}
